package org.getOffer.offer10;

/**
 * @Author yu
 * @Date 2021/10/10
 */
public class Solution {

    public static void main(String[] args) {

        Solution solution = new Solution();
        System.out.println(solution.fib(48));

    }

    public int fib(int n) {

        if (n == 0) {
            return n;
        }

        int x = 0, y = 1, sum = 1;

        for (int i = 0; i<n-1; i++) {
            sum = (x+y) % 1000000007;
            x = y;
            y = sum;
        }
        return sum;
    }

}
